package lc20240527;

import lc20240526.ListNode;

public class MergeOrderedList {
    public static void main(String[] args) {
        ListNode l1=new ListNode(1);
        l1.next=new ListNode(2);
        l1.next.next=new ListNode(4);

        ListNode l2=new ListNode(1);
        l2.next=new ListNode(3);
        l2.next.next=new ListNode(4);
        ListNode node = mergeTwoLists1(l1, l2);
        while (node!=null){
            System.out.println(node.val);
            node=node.next;
        }
    }
    public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode p=list1;
        ListNode q=list2;
        ListNode dummy=new ListNode(0);
        ListNode res=dummy;

        while (p!=null&&q!=null){

            if (p.val<q.val){
                res.next=p;
                p=p.next;
            }else {
                res.next=q;
                q=q.next;
            }
            res=res.next;
        }
        if (p==null){
            res.next=q;
        }
        if (q==null){
            res.next=p;
        }
        return dummy.next;
    }
    public static ListNode mergeTwoLists1(ListNode list1, ListNode list2) {
        if(list1==null){
            return list2;
        }else if(list2==null){
            return list1;
        }
        else if(list1.val<list2.val){
            list1.next=mergeTwoLists(list1.next,list2);
            return list1;
        }else{
            list2.next=mergeTwoLists(list2.next,list1);
            return list2;
        }
    }
}
